class Solution {
public:
    int memo[201][201];
    int getMoneyAmount(int n) { return dfs(1, n); }
    int dfs(int i, int n) {
        if (i >= n)
            return 0;
        if (memo[i][n] != 0) {
            return memo[i][n];
        }
        int ret = INT_MAX;
        for (int k = i; k <= n; k++) {
            int left = dfs(i, k - 1);
            int right = dfs(k + 1, n);
            ret = min(ret, max(left, right) + k);
        }
        memo[i][n] = ret;
        return ret;
    }
};